/*
 * @lc app=leetcode.cn id=160 lang=cpp
 * @lcpr version=30204
 *
 * [160] 相交链表
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 方法一：先走长度差
        // if (headA == nullptr || headB == nullptr)
        //     return nullptr;
        // int n1 = 0, n2 = 0;
        // ListNode *cur = headA;
        // while (cur)
        // {
        //     n1++;
        //     cur = cur->next;
        // }
        // cur = headB;
        // while (cur)
        // {
        //     n2++;
        //     cur = cur->next;
        // }
        // ListNode *curA = headA;
        // ListNode *curB = headB;
        // if (n1 > n2)
        // {
        //     int gap = n1 - n2;
        //     for (int i = 0; i < gap; ++i)
        //     {
        //         curA = curA->next;
        //     }
        //     while (curA && curB && curA != curB)
        //     {
        //         curA = curA->next;
        //         curB = curB->next;
        //     }
        // }
        // else
        // {
        //     int gap = n2 - n1;
        //     for (int i = 0; i < gap; ++i)
        //     {
        //         curB = curB->next;
        //     }
        //     while (curA && curB && curA != curB)
        //     {
        //         curA = curA->next;
        //         curB = curB->next;
        //     }
        // }
        // if (curA == nullptr)
        //     return nullptr;
        // else
        //     return curA;

        // 方法二：双指针
        // 两个指针既遍历A链表又遍历B链表，最后走的步数都是m+n长，相当于两个长度相同的链表找交点，如果有交点就会停下。
        ListNode *A = headA, *B = headB;
        while (A != B)
        {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};
// @lc code=end

/*
// @lcpr case=start
// 8\n[4,1,8,4,5]\n[5,6,1,8,4,5]\n2\n3\n
// @lcpr case=end

// @lcpr case=start
// 2\n[1,9,1,2,4]\n[3,2,4]\n3\n1\n
// @lcpr case=end

// @lcpr case=start
// 0\n[2,6,4]\n[1,5]\n3\n2\n
// @lcpr case=end

 */
